home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgramD2.iso / Visual Database / Visual dBase v5.5 / SAMPLES1.PAK / BINTREE.PRG next >
Text File  |  1995-07-18  |  3KB  |  119 lines
  1. *******************************************************************************
  2. *  PROGRAM:      Bintree.prg
  3. *
  4. *  WRITTEN BY:   Borland Samples Group
  5. *
  6. *  DATE:         5/93
  7. *
  8. *  UPDATED:      5/95
  9. *
  10. *  VERSION:      Visual dBASE
  11. *
  12. *  DESCRIPTION:  This program illustrates the creation and traversal of a
  13. *                binary tree using the Visual dBASE object() class.  It creates
  14. *                a binary tree of client names in increasing alphabetical order,
  15. *                left to right.  It then traverses the tree in that order.
  16. *
  17. *  PARAMETERS:   None
  18. *
  19. *  CALLS:        None
  20. *
  21. *  USAGE:        Do Bintree
  22. *
  23. *******************************************************************************
  24. create session
  25. set talk off
  26. set ldCheck off
  27. clear
  28.  
  29. use clients
  30.  
  31. private t
  32. t = new Tree(contact,client_Id)
  33. ? "Scanning Clients table and building binary tree..."
  34. ?
  35.  
  36. skip
  37. scan rest
  38.   ?? '.'
  39.   t.AddTree(contact,client_Id)
  40. endscan
  41.  
  42. wait "Press any key to begin in-order traversal of binary tree..."
  43.  
  44. t.InOrder()
  45.  
  46. wait
  47.  
  48.  
  49. *******************************************************************************
  50. *******************************************************************************
  51. class Tree(newKey,newValue)
  52.  
  53. * Creates binary tree.
  54. *******************************************************************************
  55.  
  56. * Constructor
  57.  
  58. this.key = newKey
  59. this.val = newValue
  60. this.left = .F.
  61. this.right = .F.
  62.  
  63.  
  64.    ****************************************************************************
  65.    procedure InOrder
  66.  
  67.    * Orders binary tree from left to right.
  68.    ****************************************************************************
  69.  
  70.    * left
  71.    if .not. empty(this.left)
  72.       this.left.InOrder()
  73.    endif
  74.  
  75.    * itself
  76.    ?  this.key, this.val
  77.  
  78.    * right
  79.    if .not. empty(this.right)
  80.       this.right.InOrder()
  81.    endif
  82.  
  83.  
  84.    ****************************************************************************
  85.    procedure AddTree(newKey,newValue)
  86.  
  87.    * Adds a new node to the tree.
  88.    ****************************************************************************
  89.  
  90.    this.Insert(new Tree(newKey, newValue))
  91.  
  92.  
  93.    ****************************************************************************
  94.    procedure Insert(o)
  95.  
  96.    * Inserts a node into an ordered tree.
  97.    ****************************************************************************
  98.  
  99.    if o.key < this.key
  100.       if (empty(this.left))
  101.          this.left = o
  102.          return(o)
  103.       else
  104.          return(this.left.Insert(o))
  105.       endif
  106.    else
  107.       if (empty(this.right))
  108.          this.right = o
  109.          return(o)
  110.       else
  111.          return(this.right.Insert(o))
  112.       endif
  113.    endif
  114.  
  115.  
  116. endclass
  117.  
  118.  
  119.